1. Field of the Invention
The present invention generally relates to computer systems and, more particularly, to a method of improving the performance of a cache used by a processor of a computer system.
2. Description of the Related Art
The basic structure of a conventional computer system 10 is shown in FIG. 1. Computer system 10 may have one or more processing units, two of which 12a and 12b are depicted, which are connected to various peripheral devices, including input/output (I/O) devices 14 (such as a display monitor, keyboard, and permanent storage device), memory device 16 (such as random access memory or RAM) that is used by the processing units to carry out program instructions, and firmware 18 whose primary purpose is to seek out and load an operating system from one of the peripherals (usually the permanent memory device) whenever the computer is first turned on. Processing units 12a and 12b communicate with the peripheral devices by various means, including a generalized interconnect or bus 20. Computer system 10 may have many additional components which are not shown, such as serial and parallel ports for connection to, e.g., modems or printers. Those skilled in the art will further appreciate that there are other components that might be used in conjunction with those shown in the block diagram of FIG. 1; for example, a display adapter might be used to control a video display monitor, a memory controller can be used to access memory 16, etc. Also, instead of connecting I/O devices 14 directly to bus 20, they may be connected to a secondary (I/O) bus which is further connected to an I/O bridge to bus 20. The computer can have more than two processing units.
In a symmetric multi-processor (SMP) computer, all of the processing units are generally identical, that is, they all use a common set or subset of instructions and protocols to operate, and generally have the same architecture. A typical architecture is shown in FIG. 1. A processing unit includes a processor core 22 having a plurality of registers and execution units, which carry out program instructions in order to operate the computer. An exemplary processing unit includes the PowerPC.TM. processor marketed by International Business Machines Corp. The processing unit can also have one or more caches, such as an instruction cache 24 and a data cache 26, which are implemented using high speed memory devices. Caches are commonly used to temporarily store values that might be repeatedly accessed by a processor, in order to speed up processing by avoiding the longer step of loading the values from memory 16. These caches are referred to as "on-board" when they are integrally packaged with the processor core on a single integrated chip 28. Each cache is associated with a cache controller (not shown) that manages the transfer of data between the processor core and the cache memory.
A processing unit 12 can include additional caches, such as cache 30, which is referred to as a level 2 (L2) cache since it supports the on-board (level 1) caches 24 and 26. In other words, cache 30 acts as an intermediary between memory 16 and the on-board caches, and can store a much larger amount of information (instructions and data) than the on-board caches can, but at a longer access penalty. For example, cache 30 may be a chip having a storage capacity of 256 or 512 kilobytes, while the processor may be an IBM PowerPC.TM. 604-series processor having on-board caches with 64 kilobytes of total storage. Cache 30 is connected to bus 20, and all loading of information from memory 16 into processor core 22 usually comes through cache 30. Although FIG. 1 depicts only a two-level cache hierarchy, multi-level cache hierarchies can be provided where there are many levels of interconnected caches.
A cache has many "blocks" which individually store the various instructions and data values. The blocks in any cache are divided into groups of blocks called "sets" or "congruence classes." A set is the collection of cache blocks that a given memory block can reside in. For any given memory block, there is a unique set in the cache that the block can be mapped into, according to preset mapping functions. The number of blocks in a set is referred to as the associativity of the cache, e.g. 2-way set associative means that for any given memory block there are two blocks in the cache that the memory block can be mapped into; however, several different blocks in main memory can be mapped to any given set. A 1-way set associate cache is direct mapped, that is, there is only one cache block that can contain a particular memory block. A cache is said to be fully associative if a memory block can occupy any cache block, i.e., there is one congruence class, and the address tag is the full address of the memory block.
An exemplary cache line (block) includes an address tag field, a state bit field, an inclusivity bit field, and a value field for storing the actual instruction or data. The state bit field and inclusivity bit fields are used to maintain cache coherency in a multiprocessor computer system (indicate the validity of the value stored in the cache).
The address tag is a subset of the full address of the corresponding memory block. A compare match of an incoming address with one of the tags within the address tag field indicates a cache "hit." The collection of all of the address tags in a cache (and sometimes the state bit and inclusivity bit fields) is referred to as a directory, and the collection of all of the value fields is the cache entry array.
When all of the blocks in a congruence class for a given cache are full and that cache receives a request, whether a "read" or "write," to a memory location that maps into the full congruence class, the cache must "evict" one of the blocks currently in the class. The cache chooses a block by one of a number of means known to those skilled in the art (least recently used (LRU), random, pseudo-LRU, etc.) to be evicted. If the data in the chosen block is modified, that data is written to the next lowest level in the memory hierarchy which may be another cache (in the case of the L1 or on-board cache) or main memory (in the case of an L2 cache, as depicted in the two-level architecture of FIG. 1). By the principle of inclusion, the lower level of the hierarchy will already have a block available to hold the written modified data. However, if the data in the chosen block is not modified, the block is simply abandoned and not written to the next lowest level in the hierarchy. This process of removing a block from one level of the hierarchy is known as an "eviction". At the end of this process, the cache no longer holds a copy of the evicted block.
FIG. 2 illustrates the foregoing cache structure and eviction process. A cache 40 (L1 or a lower level) includes a cache directory 42, a cache entry array 44, an LRU array 46, and control logic 48 for selecting a block for eviction from a particular congruence class. The depicted cache 40 is 8-way set associative, and so each of the directory 42, cache entry array 44 and LRU array 46 has a specific set of eight blocks for a particular congruence class as indicated at 50. In other words, a specific member of the congruence class in cache directory 42 is associated with a specific member of the congruence class in cache entry array 44 and with a specific member of the congruence class in LRU array 46, as indicated by the "X" shown in congruence class 50.
Each of the blocks in directory 42 are connected to the control logic via an error correction code (ECC) circuit 52. A bit in a given cache block may contain an incorrect value, either due to a soft error (such as stray radiation or electrostatic discharge) or to a hard error (a defective cell). ECCs can be used to reconstruct the proper data stream. Some ECCs can only be used to detect and correct single-bit errors, i.e., if two or more bits in a particular block are invalid, then the ECC might not be able to determine what the proper data stream should actually be, but at least the failure can be detected. Other ECCs are more sophisticated and even allow detection or correction of double errors. These latter errors are costly to correct, but the design tradeoff is to halt the machine when double-bit errors occur. Although only directory 42 is shown with ECC circuits, these circuits can similarly be used with other arrays, such as cache entry array 44.
The outputs of ECC circuits 52, whose values correspond to (corrected) memory block addresses, are connected to respective comparators 54 each of which also receives the address of the requested memory block. If a valid copy of a requested memory block is in the congruence class 50, then one, and only one, of the comparators 54 will output an active signal. The outputs of comparators 54 are connected to a multiplexer 56 and also to an OR gate 58, whose output controls multiplexer 56. If a cache hit occurs (a requested address matches with an address in cache directory 42), then OR gate 58 activates multiplexer 56 to pass on a signal indicating which member of the congruence class matches the address. This signal controls another multiplexer 60 which receives inputs from each of the entries in cache entry array 44. In this manner, when a cache hit in the directory occurs, the corresponding value is passed through multiplexer 60 to a bus 62.
If a cache miss occurs, and if all of the blocks in the particular congruence class 50 already have valid copies of memory blocks, then one of the cache blocks in congruence class 50 must be selected for victimization. This selection is performed using the LRU bits for the congruence class in LRU array 46. For each cache block in the class, there are a plurality of LRU bits, for example, three LRU bits per block for an 8-way set associative cache. The LRU bits from each block in the class are provided as inputs to a decoder 64 having an 8-bit output to indicate which of the blocks is to be victimized. This output is coupled to multiplexer 56. In this manner, if OR gate 58 is not active, multiplexer 56 passes on an indication of the cache block to be used based on the outputs of decoder 64.
The ECC circuits discussed above are one way to deal with soft errors arising in memory cells. Another approach used for dealing with hard errors is to provide redundancy within the arrays (directory, LRU, cache). When a cache chip is fabricated, it can be tested to determine if there are any defective row or column lines in each of the arrays (row and column lines are tested for the entire cache directory, and LRU. If an array is defective, a fuse can be permanently blown to indicate its defective nature. A comparison is then made inside the array for each accessed address to see if it matches with a defective address. If so, appropriate logic re-routes the address to one of many extra row and column lines formed on the chip, i.e., from redundant bit lines (columns) and word lines (rows). The number of extra bit and word lines may vary depending upon the defect rate and desired chip yield. For a low-defect (larger physical size) cache, two extra lines might be provided for every 256 regular lines, while in a high-defect (smaller physical size) cache, two extra lines might be provided for every eight regular lines.
There are several disadvantages and limitations in the foregoing cache construction. With respect to ECC circuits 52, these circuits are fairly complex and not only take up space on the chip, but further slow down processing since they are in the critical (timing) path for retrieving the cached values (either from directory or cache). The ECC circuits might allow for correction of double bit errors, but not for multiple bit errors with more than two bad bits. Another aspect of these prior art cache constructions that adds complexity and slows down processing is the arbitration logic 66 that is required to selectively interconnect the cache with the CPU, for CPU snoops, or with the system bus, for system bus snoops. This logic is again in the critical path. Such use of a single cache by two snooping devices inherently gives rise to certain other delays, such as when both the CPU and the system bus want to perform a read on the cache at the same time; the two read operations cannot be performed simultaneously, but must be serialized by the arbitration logic. The same is true for write operations.
Another disadvantage in cache construction relates to the use of bit line redundancy and word line redundance. While this technique can increase chip yield, the redundancies get directly in the critical path for array access. Extra time is required to search against defective row and column lines, and to re-direct requests that match with a defective line. So the tradeoff is a higher yield versus slower cache response. Another disadvantage is the additional physical size that must be provided for the redundant lines. In the example where two extra lines were provided for every 8 regular lines, 25% extra cache size (overhead) is required, and much of this space will never even be used. Redundant lines also do not scale particularly well, e.g., if the cache line size was doubled (from say 64 bytes to 128 bytes), the amount of silicon (chip space) required for the redundant lines will likewise double. Finally, the use of redundant lines which are used based on fuses blown in the cache is static and fairly wasteful. The availability of the redundant lines is based on the state of the cache during testing. In high density, large cache chips operating under varying conditions of junction temperature and internal voltages, defects in the cache build but these additional defective lines cannot be re-directed. Not only must numerous extra lines be provided to increase yield, but many of those lines are never even used.
In light of the foregoing, it would be desirable to provide a cache construction having improved handling of defective cache lines, including speeding up cache access and providing exceptional error correction capability. It would be further advantageous if the cache construction provided for efficient and dynamic use of all available cache lines without complicated logic circuits, and scaled appropriately to larger cache lines.